﻿namespace Busconeitor.Domain.Utils.HashTable
{
    using System;
    using System.Text;
    using SimpleList;

    [Serializable]
    public class HashTable
    {
        private SimpleList[] _items;
        private Type _clase;   // la clase de objetos que contiene la tabla

        /// <summary>
        /// Crea una tabla hash con tamaño 10 por defecto. El valor 11 es el primer
        /// número primo mayor a 10, y se eligió por su cercanía con el valor
        /// "típico" de 10.
        /// </summary>
        public HashTable()
            : this(10)
        {
        }

        /// <summary>
        /// Crea una tabla hash con tamaño n. Si n es cero o negativo, el tamaño se
        /// ajusta a 11. Este constructor no controla si n es primo, ni busca el
        /// siguiente primo mayor a n.
        /// </summary>
        /// <param name="n">el tamaño de la tabla a crear.</param>
        public HashTable(int n)
        {
            if (n <= 0)
            {
                n = 11;
            }

            _items = new SimpleList[n];

            for (var i = 0; i < n; i++)
            {
                _items[i] = new SimpleList();
            }
        }

        public virtual void Put(IComparable x)
        {
            if (x != null)
            {
                // capturamos la clase del primer objeto que entró en la tabla...
                if (_clase == null)
                {
                    _clase = x.GetType();
                }

                // control de homogeneidad a nivel tabla...
                if (x.GetType() != _clase)
                {
                    return;
                }

                // controlamos si es hora de redispersar...
                if (AverageLength() >= 3)
                {
                    Rehash();
                }

                // ahora si: primero tomamos el hashCode() del objeto...
                var k = x.GetHashCode();
                // ... luego dispersamos la clave...
                var y = HashFunction(k);
                // ... y finalmente pedimos a la lista que corresponda que haga la inserción
                _items[y].AddFirst(x);
            }
        }

        /// <summary>
        /// Elimina el objeto x de la tabla. No hace nada si 'x' no es de la misma clase 
        /// que los objetos que ya estaban en la tabla, o si 'x' no estaba en la tabla.
        /// </summary>
        /// <param name="x">el objeto a eliminar.</param>
        public void Remove(IComparable x)
        {
            // si no hay nada en la tabla, sale sin hacer nada...
            if (_clase == null)
            {
                return;
            }

            if (x != null)
            {
                // control de homogeneidad a nivel tabla...
                if (x.GetType() != _clase)
                {
                    return;
                }

                var k = x.GetHashCode();
                var y = HashFunction(k);
                _items[y].Remove(x);
            }
        }

        /// <summary>
        /// Busca el objeto x en la tabla, y retorna la dirección del objeto que esté 
        /// en la tabla y coincida con x, o null si x no existía en la tabla o no era
        /// de la misma clase que el contenido de la tabla.
        /// </summary>
        /// <param name="x">el objeto a buscar</param>
        /// <returns>la dirección del objeto que coincide con x en la tabla, o null si no existía.</returns>
        public IComparable Get(IComparable x)
        {
            // si no hay nada en la tabla, sale sin hacer nada...
            if (_clase == null)
            {
                return null;
            }

            if (x != null)
            {
                // control de homogeneidad a nivel tabla...
                if (x.GetType() != _clase)
                {
                    return null;
                }

                var k = x.GetHashCode();
                var y = HashFunction(k);
            
                return _items[y].Search(x);
            }

            return null;
        }

        /// <summary>
        /// Comprueba si x está en la tabla y retorna true en ese caso, o retorna
        /// false si x no existe en la tabla o no es de la misma clase que el
        /// contenido de la tabla.
        /// </summary>
        /// <param name="x">el objeto a buscar.</param>
        /// <returns>true si 'x' está en la tabla.</returns>
        public Boolean Contains(IComparable x)
        {
            // si no hay nada en la tabla, sale sin hacer nada...
            if (_clase == null)
            {
                return false;
            }

            if (x != null)
            {
                // control de homogeneidad a nivel tabla...
                if (x.GetType() != _clase)
                {
                    return false;
                }

                var k = x.GetHashCode();
                var y = HashFunction(k);
            
                return _items[y].Contains(x);
            }

            return false;
        }

        /// <summary>
        /// Devuelve el contenido de la tabla en forma de String.
        /// </summary>
        /// <returns>un String con el contenido de la tabla.</returns>
        public override String ToString()
        {
            var cad = new StringBuilder();
            
            for (var i = 0; i < _items.Length; i++)
            {
                cad.Append("\nLista " + i + ":\n\t" + _items[i].ToString());
            }
            
            return cad.ToString();
        }

        /// <summary>
        /// Calcula la longitud promedio de las listas de la tabla.
        /// </summary>
        /// <returns>la longitud promedio de la listas contenidas en la tabla.</returns>
        private int AverageLength()
        {
            var ac = 0;

            for (var i = 0; i < _items.Length; i++)
            {
                ac += _items[i].Size();
            }

            return ac / _items.Length;
        }

        /// <summary>
        /// Incrementa el tamaño de la tabla y reorganiza su contenido. Se invoca
        /// automáticamente cuando se detecta que el promedio de nodos por lista
        /// supera a cierto valor crítico (que en nuestra implementación de es de 3
        /// nodos por lista, aunque sería aceptable hasta unos 10 nodos por lista)
        /// </summary>
        protected void Rehash()
        {
            // calculamos un aumento del 50% sobre el tamaño anterior... aunque no busco un número primo...
            var n = (int)(1.5 * _items.Length);
            // creamos un nuevo arreglo de listas, de ese tamaño...
            var temp = new SimpleList[n];

            for (var j = 0; j < temp.Length; j++)
            {
                temp[j] = new SimpleList();
            }

            // recorremos la vieja tabla, para extraer uno a uno los objetos que contenía...
            for (var i = 0; i < _items.Length; i++)
            {
                // entramos en la lista número i, y la recorremos con el iterador...
                _items[i].StartIterator();

                while (_items[i].HasNext())
                {
                    // obtenemos un objeto de la vieja lista...
                    var x = _items[i].Next();
                    // obtenemos su nuevo valor de dispersión para el nuevo arreglo...
                    var k = x.GetHashCode();
                    var y = k % temp.Length;
                    // y lo insertamos en el nuevo arreglo, en la lista número "y"...
                    temp[y].AddFirst(x);
                }
            }
            // cambiamos la referencia items para que apunte a la nueva tabla...
            _items = temp;
        }

        /// <summary>
        /// Función hash. Toma el hashCode() de un objeto, y retorna un índice para
        /// entrar en el arreglo items.
        /// </summary>
        /// <param name="k">el valor hashCode del objeto a almacenar.</param>
        /// <returns>el índice para entrar en la tabla items.</returns>
        private int HashFunction(int k)
        {
            return Math.Abs(k % _items.Length);
        }
    }
}
